Міністерство освіти та науки України
Національний університет “Львівська політехніка”
ІКТАМ
Кафедра ЕОМ
Курсова робота
з курсу „Програмування”
”Структури даних та алгоритми”
Виконав: ст. гр. КІ-
Прийняла:
Львів 2003
Завдання на курсову роботу
Завдання 1
Дослідити представлення в пам’яті комп’ютера даних статичної структури. Розглянути основні прості (цілі, дійсні, символьні, логічні) і складові або фундаментальні (масиви, записи, рядки символів) структури даних:
const zz1= місяць народження (дві цифри);
zz2= дві останні цифри року народження; *
zz3= zz2-30;
var b1 : Boolean;
b2 : Wordbool;
b3 : Longbool;
ch : Char;
i1 : Byte;
i2 : Shortint;
i3 : Word;
i4 : Integer;
i5 : Longint;
r1 : Real;
r2 : Single;
r3 : Double;
r4 : Extended;
r5 : Comp;
str : String [15];
p : (Прізвище, Ім’я, По-батькові); **
d : zz1 .. zz2;
m : array [1..2, 1..5] of char;
rec : record
a1, a2 : string[15];
b1, b2, b3 : char;
c1, c2 : integer
end;
s : set of zz1 .. zz3 ;
f : text;
- - - - - - - - - -
* - Замість місяця і року народження підставляти свої конкретні дати (по дві цифри кожна).
** - Замість Прізвище, Ім’я, По-батькові підставляти свої конкретні значення, записані латинськими літерами ( перша літера - велика, решта – малі) .
Тестування провести для наступних значень змінних:
true, якщо день народження парне число;
b1 =
false, якщо день народження непарне число;
b2 := succ(b1);
b3 := pred(pred(b1));
ch – перша літера Прізвища (велика українська літера);
i1 – день народження;
i2 := -i1;
i3 := i1*125;
i4 := -i3;
i5 := -i3;
r1– дробове число: ціла частина – місяць народження, дробова частина - рік народження;
r2 := r1*125;
r3 := -r2;
r4 := r2;
r5 := i5;
{ Наприклад, якщо дата народження 21.10.1982, то:
i1 := 21; i2 := -21; i3 := 2625; i4 := 2625; i5 := -2625;
r1 := 10.1982; r2 := 1274.775; r3 := -1274.775; r4:= 1274.775; r5 := -2625; }
str – Прізвище ( українські літери, перша - велика, решта - малі);
p – Ім’я ( латинські літери, перша - велика, решта - малі);
d – число, яке відповідає дню народження + 15;
m[1,1] – символ, який відповідає першій цифрі номера домашнього телефону;
m[1,2] – символ, який відповідає другій цифрі;
m[1,3] := ’0’;
m[1,4] – символ, який відповідає третій цифрі;
m[1,5] := ’0’;
m[2,1] := ’0’;
m[2,2] - символ, який відповідає четвертій цифрі;
m[2,3] := ’0’;
m[2,4] - символ, який відповідає п’ятій цифрі;
m[2,5] - символ, який відповідає шостій цифрі;
{Якщо домашнього телефону немає, обрахунки проводити для кафедрального телефону, його номер 398196: m[1,1]:=’3’; m[1,2]:=’9’; m[1,4]:=’8’; m[2,2]:=’1’; m[2,4]:=’9’; m[2,5]:=’6’;}
rec.a1 – назва міста в адресі прописки ( українські літери, перша - велика, решта - малі);
rec.a2 – назва вулиці в адресі прописки ( українські літери, перша - велика, решта - малі);
rec.с1 – номер будинку в адресі прописки;
rec.с2 – номер квартири в адресі прописки;
rec.b1 := ’,’ ;
rec.b2 := ’,’ ;
rec.b3 := ’/’ ;
S – множина всіх чисел кратних k з діапазону zz1 .. zz3,
( k = № mod 5 + 2 , де № - порядковий номер студента в журналі викладача );
Завдання 2
Реалізувати метод Сортування Шелла та Індексно-послідовного пошуку в послідовності, представленій у вигляді масиву чисел, елементи якого містять по декілька інформаційних полів (в загальному випадку – великі об’єми інформації), одне з яких є ключовим.
Намалювати схему алгоритму для конкретного прикладу послідовності з десяти цілих чисел зі знаком.
Дослідити метод сортування Шелла на стійкіть.
Дослідити ефективність метода. Для цього визначити середні значення кількості порівнянь, кількості перестановок і часу виконання. Порівняти отримані характеристики з аналогічними даними для основних простих методів сортування (вставки, вибору, обміну), зробити висновки про ефективність ме...
